package org.example.myleet.p869;

import java.util.Arrays;

public class Solution {

    /**
     * 官方思路：逆向思维，先求出题目数据范围内所有2的幂，然后逐个和n比较字符频次，速度快
     */
    public boolean reorderedPowerOf2(int n) {
        if ((n & (n - 1)) == 0) {
            return true;
        }
        //先求出n的字符频次
        String nStr = Integer.toString(n);
        int[] nCharFreq = new int[10];
        for (char c : nStr.toCharArray()) {
            ++nCharFreq[c - '0'];
        }
        int num = 1;
        for (;;) {
            String numStr = Integer.toString(num);
            if (numStr.length() == nStr.length()) {
                //num的长度和n的长度相等，统计字符频次后，尝试比较
                int[] numCharFreq = new int[10];
                for (char c : numStr.toCharArray()) {
                    ++numCharFreq[c - '0'];
                }
                boolean found = true;
                for (int i = 0; i < 10; ++i) {
                    if (nCharFreq[i] != numCharFreq[i]) {
                        //有一个对不上就排除
                        found = false;
                        break;
                    }
                }
                if (found) {
                    return true;
                }
            }
            if (num > 1000000000) {
                //num超出题目数据范围后停止
                break;
            }
            //下一个2的幂
            num *= 2;
        }
        return false;
    }

    /**
     * 传统思路：全排列枚举+位运算判断
     */
    public boolean reorderedPowerOf2_2(int n) {
        if (isPowerOf2(n)) {
            return true;
        }
        char[] nums = Integer.toString(n).toCharArray();
        Arrays.sort(nums);
        do {
            if (nums.length > 1 && nums[0] == '0') {
                continue;
            }
            if (isPowerOf2(Integer.parseInt(new String(nums)))) {
                return true;
            }
        } while (nextPermutation(nums));
        return false;
    }

    /**
     * 获取下一个字典序
     * 1、从字符串右边开始向左边查找，找到第一个右邻更大的位置，记为i
     * 2、从字符串右边开始向左查找至i+1位，找到比i位大的位置，记为j
     * 3、交换i和j的字符
     * 4、从i+1位至字符串末尾进行翻转（实际上就是变成非递减顺序）
     * 5、重复1～4步直至找不到满足第1步的情况，字典序最大
     */
    private boolean nextPermutation(char[] nums) {
        for (int i = nums.length - 2; i >= 0; --i) {
            if (nums[i] < nums[i + 1]) {
                for (int j = nums.length - 1; j > i; --j) {
                    if (nums[i] < nums[j]) {
                        char t = nums[i];
                        nums[i] = nums[j];
                        nums[j] = t;
                        int l = i + 1, r = nums.length - 1;
                        while (l < r) {
                            t = nums[r];
                            nums[r] = nums[l];
                            nums[l] = t;
                            ++l;
                            --r;
                        }
                        break;
                    }
                }
                return true;
            }
        }
        return false;
    }

    private boolean isPowerOf2(int n) {
        if (n < 1) {
            return false;
        }
        return (n & (n - 1)) == 0;
    }
}
